1. Field of the Invention
This invention relates to a multiplier apparatus for multiplying integers and, more particularly, to an multiplier apparatus which is suitable for a cryptographic scheme using a cryptographic system such as the RSA cryptosystem, and which multiplies integers of many figures by utilizing multiplication of a small number of figures.
2. Description of the Related Art
Recently, with the rapid development of information communication systems using computer networks, the importance of cryptographic schemes for data protection has increased.
There are two kinds of cryptosystems: public-key cryptosystems and common-key cryptosystems. Unlike common-key cryptosystems, public-key cryptosystems are advantageous in that key management is easy and digital signature is possible. In the RAS cryptosystem, which is typical of public-key cryptosystems, a cryptogram is calculated by a modular exponentiation: C=M.sup.e mod N (C, M, N, e: integers). The modular exponentiation is realized by repeating a modular multiplication: D=A.multidot.B mod N (A, B, D: integers). To ensure security against cryptanalysis, 512 bits or more are required for the values N and e. In such a case, the computational complexity is very high.
To directly execute the above-described calculation, a multiplier and a divider having many places are required. In gate array design or board design, a multiplier for multiplying integers of a small number of figures can be easily arranged because suitable cell libraries, transistor-transistor logic (TTL) devices and the like are available. However, there have been provided no ROMs and no cell libraries for realizing a multiplier and a divider of many places. It has been difficult to design a multiplier or a divider of many places in accordance with one's need, because the circuit configuration is very complicated if the configuration of a multiplier or a divider of a small number of places is simply extended.
Then, a multiplication may be performed by partitioning an input value with respect to a predetermined number of bits. In a calculation system such as a Galois field using no carry, a multiplication can be executed by a circuit such as that shown in FIG. 2. The circuit shown in FIG. 2 has (m.times.m)-bit multipliers .times.Bi on a Galois field having m-bit values Bi(i=1, . . . , n-1) as multiplier factors, m-bit EXOR devices EX, and m-bit registers r.
In the case of an ordinary multiplication of integers performed by separate operations of such a circuit, however, a carry occurs when each separate operation is performed. It is therefore difficult to form an efficient multiplication apparatus by using this circuit.